/**
 * @Author: linzp
 * @Date: 2021/12/21/11:40
 */
public class solution43 {
    //写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
    //例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？
    //一般while(left <= right)&right = middle - 1   while(left < right)&right = middle
    //https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#_704-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE
}

/**
 * 704. 二分查找
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 *
 * 示例 1:
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 9
 * 输出: 4
 * 解释: 9 出现在 nums 中并且下标为 4
 */
class Solution704 {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        //左闭右闭即[left, right]定义
        while (left <= right) {//right=mid-1，这样就不会错过targer=right了
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        /**
         *
         *  int left = 0, right = nums.length;
         *   //左闭右开即[left, right)定义
         *         while (left < right) {// num[mid]!=target right=mid left=right没意义 答案不会是right (midle变成right 也就是right不会是target 那么left=right还需要看嘛 所以边界就是<)
         *             int mid = left + ((right - left) >> 1);
         *             if (target == nums[mid]) {
         *                 return mid;
         *             } else if (target > nums[mid]) {
         *                 left = mid + 1;
         *             } else {
         *                 right = mid ;
         *             }
         *         }
         */
        return -1;
    }
}

/**
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 */
class Solution35 {
    public int searchInsert(int[] nums, int target) {


        int left = 0, right = nums.length - 1;
        //左闭右闭即[left, right]定义
        while (left <= right) {//right=mid-1，这样就不会错过targer=right了
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;//退出循环时 会有个交叉交换l和right 这时的l已经+1了 所以直接返回即可。

        /**
         *   int left = 0, right = nums.length;
         *   //左闭右开即[left, right)定义
         *         while (left < right) {// num[mid]!=target right=mid left=right没意义 答案不会是right
         *             int mid = left + ((right - left) >> 1);
         *             if (target == nums[mid]) {
         *                 return mid;
         *             } else if (target > nums[mid]) {
         *                 left = mid + 1;
         *             } else {
         *                 right = mid ;
         *             }
         *         }
         *           return left;
         */

    }
}
/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 进阶：
 *
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 *
 *
 * 示例 1：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 */
class Solution34 {
    public int[] searchRange(int[] nums, int target) {

    }
}
